//Problem Id:1011  User Id:tq 
//Memory:220K  Time:406MS
//Language:C++  Result:Accepted
/*
	author: TangQiao @ Wind 
	problem name: The Tower of Babylon
	source : ULM 1996
	problem type: 动态规划
	problem description: 给你各种各样大小的方块,规定各种方块可以无限地取,但是每一个方块必须放在长宽都比它大的
		上面,问最高可以放多高.N(方块的种数)最大为30
	problem solution: tt[]存读入数据, tu[][]用于递推的数组. 对于一种方块,由于可以选不同的面作为长宽,故对应有三
			  种取法.所以tt的上界为30*3 ~= 100
			  with tu[i][j] do :
			  	h:表示第i种方块,上面放j个方块时可以放到的最大高度.
			  	x,y表示第i种方块为底,底的长和宽.
			  	tox,toy表示第i种方块,上面放j个方块时可以放到的最大高度时,最顶上的长和宽.
			  
			  递推公式: tu[i][1]就是方块本身.
			  	    tu[i][2]=Max ( tu[i][1]+tu[j][1]) j=1..tot
			  	    tu[i][3]=Max ( tu[i][1]+tu[j][2]
			  	    		  || tu[i][2]+ tu[j][1]) j=1..tot
			  	    tu[i][k]=Max ( tu[i][l]+tu[j][n-l]) l=1..n-1; j=1..tot
	award:  差不多算是第一次自己想到用动规,并且自己实现了具体的动规算法.		  	  
		可以看到,其实运行效率是很低的,用了400多ms,而其他人都只用了15ms.
		不过,经过这一次,让我对于动态规划题不再害怕.相信自己以后可以更加
		努力做好动态规划题.
	another solution: 邓子睿事先把方块的长宽进行了排序,这样,第i个方块上可以放的,只可能是i+1 ~ tot 之间的方块,
			  这样,就可以少判断很多,如果说我的算法是O(n*n) 的话,他的应该是O(n*log(n)
	date : 2005.5.20 北师大校队个人选拨赛1
*/
#include <stdio.h>
#include <string.h>
#include <math.h>

struct ttdeff
{
	int x,y;
	int h;
}tt[100];

struct ttdef2
{
	int x,y,h;
	int tx,ty;
}tu[100][100];

int tot;
int n;
int n3;

void init()
{
	int i;
	int a,b,c;

	tot=0;
	memset(tu,0,sizeof(tu));
	memset(tt,0,sizeof(tt));
	for (i=1;i<=n;i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		tt[++tot].x=a;
		tt[tot].y=b;
		tt[tot].h=c;

		tt[++tot].x=a;	
		tt[tot].y=c;
		tt[tot].h=b;

		tt[++tot].x=b;
		tt[tot].y=c;
		tt[tot].h=a;
		
	}
}

void sort()
{
	int i,j;
	for (i=1;i<=tot;i++)
		if (tt[i].x <tt[i].y)
		{
			j=tt[i].x;
			tt[i].x=tt[i].y;
			tt[i].y=j;
		}
}

main()
{
	int i,j,k,l;
	int max, tox, toy;
	int yuan,zhao;
	int mmx;
	int time,n2;

	time=0;
	while (1)
	{
		scanf("%d", &n);
		if (n==0) break;
		time++;
		init();
		sort();
	
		n3=n*3;
		n2=n*2;
		mmx=1;
		for (i=1;i<=tot;i++)
		{
			tu[i][1].x=tt[i].x;
			tu[i][1].y=tt[i].y;
			tu[i][1].h=tt[i].h;
			tu[i][1].tx=tt[i].x;
			tu[i][1].ty=tt[i].y;
		}

		for (k=2;k<=n2;k++)
		{
			for (i=1; i<=tot; i++)
			{
				max=0;				
				for (j=1; j<k; j++)
				{					
					if (tu[i][j].tx==0) continue;
					for (l=1;l<=tot;l++)
					{
						if (tu[i][j].tx > tu[l][k-j].x && tu[i][j].ty > tu[l][k-j].y
							&& max< tu[i][j].h+tu[l][k-j].h)
						{
							max=tu[i][j].h+tu[l][k-j].h;
							tox=tu[l][k-j].tx;
							toy=tu[l][k-j].ty;
						}

					}
				}
				if (max!=0)
				{
					tu[i][k].x=tt[i].x;
					tu[i][k].y=tt[i].y;
					tu[i][k].h=max;
					if (mmx<max) mmx=max;
					tu[i][k].tx=tox;
					tu[i][k].ty=toy;
				}
				
			}

		}
		printf("Case %d: maximum height = %d\n",time,mmx);


	}//end of while 

	return 0;
}

